//  NOTE: should be moved to .cpp to save mem
//
//  BKTree.h
//
//  Created by Rune Juul Laugesen on 10/11/13.
//  Copyright (c) 2013 Rune Juul Laugesen. All rights reserved.
//

#ifndef __Test__BKTree__
#define __Test__BKTree__

#include <iostream>
#include <map>
#include <cmath>
#include <vector>
#include "BKTreeNode.h"


using namespace std;

class BKTree
{
private:
    BKTreeNode *_root;
    map<char, string> _alphabet;
    map<string, string> _dictionary;
    
    void insertChild(BKTreeNode *src, BKTreeNode *child);
    void BuildAlphabet();
public:
    BKTree();
    void BuildDictionary(vector<string> dictionary);
    void Insert(string word);
    map<int, string> Search(string word, int maxdistance);
    string WordToKeys(string word);
    string KeysToWord(string keys);
};

/*
inline static int EditDistance(string s, string t)
{
    int ret = 0;
    if (s == "" || t == "")
    {
        throw "Strings must be different from null";
    }
    
    int n = s.length();
    int m = t.length();
    
    if (n == 0)
    {
        return m;
    } else if (m == 0)
    {
        return n;
    }
    
    int* p = new int[n + 1];
    int* d = new int[n + 1];
    int* swap;
    
    int cost; // cost
    
    for (int i = 0; i <= n; i++)
    {
        p[i] = i;
    }
    
    for (int j = 1; j <= m; j++)
    {
        char tj = t[j - 1];
        d[0] = j;
        
        for (int i = 1; i <= n; i++)
        {
            cost = s[i - 1] == tj ? 0 : 1;
            d[i] = min(min(d[i - 1] + 1, p[i] + 1), p[i - 1] + cost);
        }
        
        swap = p;
        p = d;
        d = swap;
    }
    ret = p[n];
    p = NULL;
    d = NULL;
    return ret;
}

template <typename KeyType, typename MetricType>
class TreeNode
{
private:
    typedef TreeNode<KeyType, MetricType> NodeType;
    
    KeyType _value;
    map<MetricType, NodeType *> *_children;
    
public:
    TreeNode(const KeyType &key) : _value(key), _children(NULL) { }
    
    ~TreeNode()
    {
        if (_children)
        {
            for (auto iter = _children->begin(); iter != _children->end(); ++iter)
                delete iter->second;
            
            delete _children;
        }
    }
    
    map<string, string> dictionary;
    
    bool Insert(NodeType *node) {
        
        if (!node)
            return false;
        
        //LevenshteinDistance d;
        int distance = EditDistance(node->_value, this->_value);
        
        if (distance == 0)
            return false;
        
        if (!_children)
            _children = new map<MetricType, NodeType *>();
        
        auto iterator = _children->find(distance);
        if (iterator == _children->end()) {
            _children->insert(std::make_pair(distance, node));
            return true;
        }
        
        return iterator->second->Insert(node);
    }
    
    multimap<MetricType, KeyType> FindWithin(const KeyType &key, MetricType d) const
    {
        multimap<MetricType, KeyType> result;
        
        findWithin(result, key, d);
        
        return result;
    }
    
    //For debugging
    void DumpTree(int depth = 0)
    {
        for (int i = 0; i < depth; ++i)
            cout << "    ";
        
        cout << this->_value << endl;
        
        if (this->hasChildren())
            for (auto iter = _children->begin(); iter != _children->end(); ++iter)
                iter->second->DumpTree(depth + 1);
    }
    
protected:
    bool hasChildren() const {
        return this->_children && this->_children->size();
    }
    
    void findWithin(multimap<MetricType, KeyType> &result, const KeyType &key, MetricType d) const
    {
        //LevenshteinDistance f;
        MetricType n = EditDistance(key, this->_value);
        
        if (n <= d)
            result.insert(pair<MetricType, KeyType>(n, this->_value));
        
        if (!this->hasChildren())
        {
            return;
        }
        
        for (auto iter = _children->begin(); iter != _children->end(); ++iter)
        {
            MetricType distance = iter->first;
            
            if (n - d <= distance && distance <= n + d)
                iter->second->findWithin(result, key, d);
        }
    }
    
};



template <typename KeyType, typename MetricType = double>
class BKTree
{
private:
    typedef TreeNode<KeyType, MetricType> NodeType;
    
    size_t m_n_nodes;
    map<string, string> _dictionary;
    map<char, string> _alphabet;

    
public:
    BKTree() : m_top(NULL), m_n_nodes(0)
    {
        // Build for Levenshtein Distance
        _alphabet.insert ( pair<char, string>('.', ".") );
        _alphabet.insert ( pair<char, string>(',', ",") );
        _alphabet.insert ( pair<char, string>('!', "!") );
        _alphabet.insert ( pair<char, string>('?', "?") );
        _alphabet.insert ( pair<char, string>('a', "a  qsw") );
        _alphabet.insert ( pair<char, string>('b', " bhnv") );
        _alphabet.insert ( pair<char, string>('c', "  cfvx") );
        _alphabet.insert ( pair<char, string>('d', " defrs") );
        _alphabet.insert ( pair<char, string>('e', " de rsw") );
        _alphabet.insert ( pair<char, string>('f', "df grt") );
        _alphabet.insert ( pair<char, string>('g', " f ght y") );
        _alphabet.insert ( pair<char, string>('h', "   ghjuy") );
        _alphabet.insert ( pair<char, string>('i', " ijko u") );
        _alphabet.insert ( pair<char, string>('j', "hijku") );
        _alphabet.insert ( pair<char, string>('k', " ijklo") );
        _alphabet.insert ( pair<char, string>('l', "   klop") );
        _alphabet.insert ( pair<char, string>('m', "   klmn") );
        _alphabet.insert ( pair<char, string>('n', " bj mn") );
        _alphabet.insert ( pair<char, string>('o', " i klop") );
        _alphabet.insert ( pair<char, string>('p', "    lop") );
        _alphabet.insert ( pair<char, string>('q', "a q w") );
        _alphabet.insert ( pair<char, string>('r', " defrt") );
        _alphabet.insert ( pair<char, string>('s', "ade  sw") );
        _alphabet.insert ( pair<char, string>('t', "  fgrt y") );
        _alphabet.insert ( pair<char, string>('u', "hij   uy") );
        _alphabet.insert ( pair<char, string>('v', " bcgv") );
        _alphabet.insert ( pair<char, string>('w', "a eq sw") );
        _alphabet.insert ( pair<char, string>('x', "  cd xz") );
        _alphabet.insert ( pair<char, string>('y', "   ghtuy") );
        _alphabet.insert ( pair<char, string>('z', "    sxz") );
        _alphabet.insert ( pair<char, string>('0', "        90") );
        _alphabet.insert ( pair<char, string>('1', "12") );
        _alphabet.insert ( pair<char, string>('2', "123") );
        _alphabet.insert ( pair<char, string>('3', " 234") );
        _alphabet.insert ( pair<char, string>('4', "  345") );
        _alphabet.insert ( pair<char, string>('5', "   456") );
        _alphabet.insert ( pair<char, string>('6', "    567") );
        _alphabet.insert ( pair<char, string>('7', "     678") );
        _alphabet.insert ( pair<char, string>('8', "      789") );
        _alphabet.insert ( pair<char, string>('9', "       890") );
    }
    
    NodeType *m_top;
    
    void BuildDictionary(vector<string> trainingdata)
    {
        for (auto it = trainingdata.begin(); it != trainingdata.end(); it++)
        {
            string word = (*it);
            Insert(WordToKeys(word));
            _dictionary.insert(pair<string, string>(WordToKeys(word),word));
        }
        
    }
    
    void Insert(const KeyType &key)
    {
        NodeType *node = new NodeType(key);
        
        if (!m_top) {
            m_top = node;
            m_n_nodes = 1;
            return;
        }
        if (m_top->Insert(node))
            ++m_n_nodes;
    };
    
    multimap<MetricType, KeyType> FindWithin(KeyType key, MetricType d) const
    {
        return m_top->FindWithin(key, d);
    }
    
    //for debugging
    void DumpTree()
    {
        m_top->DumpTree();
    }
    
    size_t size() const
    {
        return m_n_nodes;
    }
    
    string WordToKeys(string word)
    {
        string keys = "";
        map<char, string>::iterator it;

        for (int i = 0; i < word.length(); i++)
        {
            it = _alphabet.find(tolower(word[i]));
            if (it == _alphabet.end())
            {
                keys += '1';
                continue;
            }
            keys += (*it).second;
        }
        return keys;
    }
    
    string KeysToWord(string keys)
    {
        string word = "";
        map<string, string>::iterator it;
        it = _dictionary.find(keys);
        if (it != _dictionary.end()) {
            word = (*it).second;
        }
        return word;
    }
};
*/

#endif
